package com.briup.day10;

import com.briup.day10.bean.Student;

import java.util.Arrays;

/**
 * @author ThinkBook
 */
public class Test01_InsertSort {
    public static void insertionSort(int[] arr){
        /*
        * 5, 2, 6, 5, 9, 0, 3
        * 2, 5, 6, 5, 9, 0, 3
        *
        * i:1 arr[i]=2  value=2 j:0 arr[j]=5 arr[j+1]=5 j=-1 break arr[j+1=0]=2
        * i=2 arr[i]=6  value=6 j:1 arr[j]=5 break arr[j+1=2]=6
        * */
        for(int i = 1; i < arr.length; i++) {
            //i：每次要插入的元素下标
            //记录 插入元素值
            int value = arr[i];

            //内层循环：找到有序序列中合适的位置，将arr[i]插入
            int j;
            for(j = i-1; j >= 0; j--) {
                if(arr[j] > value) {
                    //arr[j]往后移
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }

            //将value插入[j+1]位置上
            if(j+1 != i) {
                arr[j+1] = value;
            }

            //每次排序后，额外输出，方便大家观察排序过程
            System.out.println(Arrays.toString(arr));
        }
    }
    public static void main(String[] args) {
        int[] array = {5,2,4,6,1,3};
        insertionSort(array);

    }
}
